package com.liyghting.datastructurealgorithm.linkedlist;

/**
 * 单向链表 插入，删除，查找 存储int数据
 * 
 * @author LiYiGuang
 * @date 2018/11/6 11:31
 */
public class SinglyLinkedList {
	private Node head = null;

	public Node findByValue(int value) {
		Node p = head;
		while (p != null && p.data != value) {
			p = p.next;
		}
		return p;
	}

	public Node findByIndex(int index) {
		Node p = head;
		int i = 0;
		while (p != null && i++ != index) {
			p = p.next;
		}
		return p;
	}

	public void insertToHead(int value) {
		if (head == null)
			head = new Node(value, null);
		else
			head = new Node(value, head);
	}

	public void insertToHead(Node newNode) {
		if (head == null) {
			head = newNode;
		} else {
			newNode.next = head;
			head = newNode;
		}

	}

	public Node insertAfter(Node p, int value) {
		Node newNode = new Node(value, null);
		insertAfter(p, newNode);
		return newNode;
	}

	public void insertAfter(Node p, Node newNode) {
		if (p == null)
			return;
		newNode.next = p.next;
		p.next = newNode;

	}

	public void insertBefore(Node p, int value) {
		Node newNode = new Node(value, null);
		insertBefore(p, newNode);
	}

	public void insertBefore(Node p, Node newNode) {
		if (p == null)
			return;
		if (head == p) {
			insertToHead(newNode);
		}

		Node q = head;
		while (q != null && q.next != p) {
			q = q.next;
		}
		if (q == null)
			return;

		newNode.next = p;
		q.next = newNode;
	}

	public void deleteByNode(Node p) {
		if (head == null || p == null)
			return;
		if (p == head) {
			head = head.next;
			return;
		}
		Node q = head;
		while (q != null && q.next != p) {
			q = q.next;
		}
		if (q == null)
			return;
		q.next = q.next.next;

	}

	public void deleteByValue(int value) {
		if (head == null)
			return;
		Node q = head;
		Node p = null;
		while (q != null && q.data != value) {
			p = q;
			q = q.next;
		}
		if (q == null)
			return;

		if (p == null) {
			head = head.next;
		} else {
			p.next = p.next.next;
		}
		// 可重复删除指定value的代码

		if (head != null && head.data == value) {
			head = head.next;
		}
		Node pNode = head;
		while (pNode != null) {
			if (pNode.next != null && pNode.next.data == value) {
				pNode.next = pNode.next.next;
				continue;
			}
			pNode = pNode.next;
		}

	}

	public void printAll() {
		Node p = head;
		while (p != null) {
			System.out.print(p.data + " ");
			p = p.next;
		}
		System.out.println();
	}

	/**
	 * 单链表反转
	 * 
	 * @return
	 */
	public SinglyLinkedList reverse() {
		SinglyLinkedList reverse = new SinglyLinkedList();
		Node headNode = null;

		Node previousNode = null;
		Node currentNode = head;
		while (currentNode != null) {
			Node nextNode = currentNode.next;
			if (nextNode == null) {
				headNode = currentNode;
			}
			currentNode.next = previousNode;
			previousNode = currentNode;
			currentNode = nextNode;
		}
		reverse.insertToHead(headNode);
		return reverse;
	}

	public static boolean checkCircle(Node list) {
		if (list == null)
			return false;
		Node slow = list;
		Node fast = list.next;
		while (slow != null && fast != null) {
			slow = slow.next;
			fast = fast.next.next;
			if (slow == fast)
				return true;
		}
		return false;
	}

	// 有序链表合并
	public static Node mergeSortedLists(Node la, Node lb) {
		if (la == null)
			return lb;
		if (lb == null)
			return la;

		Node p = la;
		Node q = lb;
		Node head;
		if (p.data < q.data) {
			head = p;
			p = p.next;
		} else {
			head = q;
			q = q.next;
		}
		Node r = head;

		while (p != null && q != null) {
			if (p.data < q.data) {
				r.next = p;
				p = p.next;
			} else {
				r.next = q;
				q = q.next;
			}
			r = r.next;
		}

		if (p != null) {
			r.next = p;
		} else {
			r.next = q;
		}

		return head;
	}

	// 删除倒数第K个结点
	public static Node deleteLastKth(Node list, int k) {
		Node fast = list;
		int i = 1;
		while (fast != null && i < k) {
			fast = fast.next;
			++i;
		}

		if (fast == null)
			return list;

		Node slow = list;
		Node prev = null;
		while (fast.next != null) {
			fast = fast.next;
			prev = slow;
			slow = slow.next;
		}

		if (prev == null) {
			list = list.next;
		} else {
			prev.next = prev.next.next;
		}
		return list;
	}

	// 求中间结点
	public static Node findMiddleNode(Node list) {
		if (list == null)
			return null;

		Node fast = list;
		Node slow = list;

		while (fast.next != null && fast.next.next != null) {
			fast = fast.next.next;
			slow = slow.next;
		}

		return slow;
	}

	public static class Node {
		private int data;
		private Node next;

		public Node(int data, Node next) {
			this.data = data;
			this.next = next;
		}

		public int getData() {
			return data;
		}
	}

	public static void main(String[] args) {
		SinglyLinkedList sl = new SinglyLinkedList();
		Node node = new Node(0, null);
		sl.head = node;
		Node newNode = sl.insertAfter(node, 1);
		newNode = sl.insertAfter(newNode, 2);
		newNode = sl.insertAfter(newNode, 3);
		sl.insertBefore(newNode, 4);
		sl.insertToHead(5);

		sl.printAll();
		sl.deleteByValue(5);
		sl.printAll();
		System.out.println(sl.findByValue(1).data);
		System.out.println(sl.findByIndex(0).data);
		System.out.println(sl.findByIndex(3).data);

		sl.reverse().printAll();
	}
}
